﻿#define _CRT_SECURE_NO_WARNINGS

#include"SList.h"


//展示
void SLTPrint(SLTNode* phead)
{
	//phead->data
	while (phead)
	{
		printf("%d->", phead->data);
		phead = phead->next;
	}
	printf("NULL\n");
}

//改变数据，将当前位置数据改变为我们想要的数值，然后将当前位置数据赋值到下一位置
//相当于当前位置插入，只是某种形式上
SLTNode* SLTInset(SLTDataType* x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}
//原来有node1->next = node2     node2->next = node3     node3->data = NULL
//然后我们让node2 = SLTInest(x)
//就相当于node2->data = x     node->next = NULL
//但要注意这时node2的地址改变了，虽然node1->next还是等于node2,但node->next不再等于node3
//相当于node1->next=node2=newnode,但是node2->next=newnode->next不等于node3

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTInset(x);
	if (*pphead == NULL)//判断一下phead是不是为空(注意phead是链表头地址)
	{					//如果为空说明整个链表为空
		*pphead = newnode;//所以这里就可以直接赋值了
	}
	else
	{
		//先找下链表尾地址
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;
	}
}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(*pphead);
	SLTNode* newnode = SLTInset(x);
	newnode->next = *pphead;
	*pphead = newnode;
}//跟上面差不多理解

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);//等价于assert(*pphead!=NULL)，注意这里已经避免了*pphead=0的情况，因此下面就不用考虑了
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//举例嘛，*pphead=node1,node1->next=node2;node2->next=NULL

		SLTNode* s1 = *pphead;//s1=node1
		SLTNode* s2 = *pphead;//s2=node1
		while (s1->next)//s1->next=node2
		{
			s2 = s1;//s2=node1
			s1 = s1->next;//s1=node2
		}
		free(s1);
		s1 = NULL;//node2=NULL
		s2->next=s1;//node1->next=NULL

		//然后结果*phead=node1,node1->next=NULL
		//完美
	}
}

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);

	SLTNode* s0 = *pphead;//标记原地址
	*pphead = (*pphead)->next;
	free(s0);//释放丢弃的地址，这里最初的地址是动态开辟的，如果不使用了，需要释放并置空
	s0 = NULL;
}

//查找，返回所查找数据链表节点
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	//找phead->data==x
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
			return pcur;
		pcur = pcur->next;
	}
	return NULL;
}

//在指定位置之前插⼊数据(这里传入链表头结点是为了找到指定节点上个节点，像下面的指定节点后插入就不需要找到指定节点上个节点)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{					//这里pos怎么传入呢，就需要用到上面刚写的SLTFind了，它返回的数据类型就是SLTNode*的
					//感觉这样写是有一些弊端的，如果传入的数据存在一样的就会很麻烦
					//但是吧，如果去处理类似身份证(不存在一样的)这样的数据就很方便了
	assert(pphead && *pphead);
	SLTNode* ptail = *pphead;
	while(ptail)
	{
		if (ptail == pos)//假如传入的pos为NULL，那么ptail一直next直到为NULL这个while循环就直接结束了，就相当于啥也没进行
		{
			SLTNode* pcur = ptail->next;
			SLTNode* newnode = SLTInset(x);//newnode->data=x;newnode->next=NULL
			ptail->next = newnode;
			newnode->next = pcur;
			return;
		}
		ptail = ptail->next;
	}

}

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	//node1->next=node2;node2->next=node3;node3->next=NULL
	//pos=node2
	//那么就需要
	//node1->next=node3
	SLTNode* ptail = *pphead;
	if (ptail == pos)
	{
		SLTPopFront(pphead);
		return;
	}
	while (ptail->next)
	{
		if (ptail->next == pos)
		{
			ptail->next = pos->next;
			free(pos);
			pos = NULL;
			return;
		}
		ptail = ptail->next;
	}
}

//在指定位置之后插⼊数据，这里不用传入头节点是因为用不到
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

	SLTNode* newnode = SLTInset(x);
	SLTNode* ptail = pos->next;
	pos->next = newnode;
	newnode->next = ptail;
}

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* ptail = pos->next;
	pos->next = ptail->next;
	free(ptail);//释放的是pos->next的原地址
	ptail = NULL;
}

//销毁链表
void SListDesTroy(SLTNode** pphead)
{
	assert(pphead && *pphead);

	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* ptail = pcur;
		pcur = pcur->next;
		free(ptail);
		ptail = NULL;
	}

	free(*pphead);
	*pphead = NULL;
}
